/*
 * Author: Xingbo Wang, Yaqin Yang, Ying Yang
 * Database Project
 * Time : spring 2011
 * */

package database;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.NotSerializableException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.*;

import database.impl.Record;

/*
 * Index process class
 * */
public class Index implements Serializable {
	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;

	protected Index(String fileName, String indexName, String column,
			Vector<Record> records) {
		this.column = column;
		this.records = records;
		this.fileName = fileName;
		this.indexName = indexName;
		bPlusTree = new BPlusTree(records);
		modCountIndex = 1;
	}

	// store the index into disk file
	public void dumpIndex() {
		if (!alive) {
			System.out.println("Error: the Index has been dropped");
			return;
		}
		try {
			String filename = fileName + "_" + indexName;
			// output the whole index into disk
			FileOutputStream fos = new FileOutputStream(filename);
			ObjectOutputStream oos = new ObjectOutputStream(fos);
			oos.writeObject(this);
			oos.close();
			fos.close();
		} catch (NotSerializableException e) {
			System.out.println("NotSerializableException!");
			e.printStackTrace();
		} catch (IOException e) {
			System.out.println("IO exception!");
		}
	}
/*
	// print index
	// public String viewIndex() {
	// if (!alive) {
	// System.out.println("Error: the Index has been dropped");
	// return null;
	// }
	// String result = "Index "+ indexName +" over column " +column +"\n\n" +
	// bPlusTree.printTree();
	// return result;
	// }
*/
	public String viewIndex() {
		if (!alive) {
			System.out.println("Error: the Index has been dropped");
			return null;
		}
		String result = "Index " + indexName + " over column " + column
				+ "\n\n";
		int levelNumber = 1;
		Iterator<RecordArray> it = getBPlusTreeIterator();
		LinkedList<ViewIndex> viewIndexs = new LinkedList<ViewIndex>();
		while (it.hasNext()) {
			RecordArray recordArray = it.next();
			String key = recordArray.getKey();
			int recordID;
			for (int i = 0; i < recordArray.size(); i++) {
				recordID = recordArray.get(i);
				viewIndexs.add(new ViewIndex(key, recordID, 0));
			}
		}
		
		if(viewIndexs.size() == 0)
			return "";
		
		ViewIndex element = null;
		ListIterator<ViewIndex> it1 = viewIndexs.listIterator();


		ArrayList<ViewIndex> parentLevel = null;
		// for the leaf level
		if (viewIndexs.size() > 8) {
			levelNumber++;
			parentLevel = new ArrayList<ViewIndex>();
			parentLevel.add(new ViewIndex("", 0, 0));

			// use iterator
			it1 = viewIndexs.listIterator();

			int counter = 0;
			while (it1.hasNext()) {
				element = it1.next();
				counter++;
				if (counter == 8) {
					
					if(!it1.hasNext())
						break;
					counter = 0;
					element = it1.next();
					it1.previous();
					it1.add(element = new ViewIndex(element.key, -1, 1));
					parentLevel.add(element);
				}
			}
			if (counter < 4 && counter > -1) {
				parentLevel.remove(parentLevel.size() - 1);
				Stack<ViewIndex> stack = new Stack<ViewIndex>();
				while (viewIndexs.getLast().recordID != -1) {
					stack.add(viewIndexs.removeLast());
				}
				viewIndexs.removeLast();
				while (viewIndexs.size()>0 && viewIndexs.getLast().recordID != -1 ) {
					stack.add(viewIndexs.removeLast());
				}
				for (int i = 0; i < 4; i++) {
					viewIndexs.add(stack.pop());
				}
				viewIndexs.add(new ViewIndex(stack.peek().key, -1, 1));
				parentLevel.add(viewIndexs.getLast());
				while (!stack.isEmpty()) {
					viewIndexs.add(stack.pop());
				}
			}
/*
			// if (remainder == 0) {
			// // /////////////////////////////////
			// // use iterator
			// for (int i = 1; i < viewIndexs.size() / 8; i++) {
			// element = viewIndexs.get(8 * i);
			// element.tabs += 1;
			// parentLevel.add(element);
			// }
			// } else if (remainder < 4) {
			// // secondLevel.add(viewIndexs.get(4));
			// for (int i = 1; i < viewIndexs.size() / 8; i++) {
			// element = viewIndexs.get(8 * i);
			// element.tabs += 1;
			// parentLevel.add(element);
			// }
			// element = viewIndexs.get(viewIndexs.size() - 4);
			// element.tabs += 1;
			// parentLevel.add(element);
			// } else {
			// for (int i = 1; i < viewIndexs.size() / 8 + 1; i++) {
			// element = viewIndexs.get(8 * i);
			// element.tabs += 1;
			// parentLevel.add(element);
			// }
			// }
*/
		}
		ArrayList<ViewIndex> currentLevel = parentLevel;
		// for the non-leaf level
		while (currentLevel != null && currentLevel.size() > 9) {
			levelNumber++;
			parentLevel = new ArrayList<ViewIndex>();
			parentLevel.add(new ViewIndex("", 0, 0));
			int remainder = currentLevel.size() % 9;
			
			if (remainder == 0) {
				for (int i = 1; i < currentLevel.size() / 9; i++) {
					element = currentLevel.get(9 * i);
					element.tabs += 1;
					parentLevel.add(element);
				}
			} else if (remainder < 5) {
				// secondLevel.add(viewIndexs.get(4));
				for (int i = 1; i < currentLevel.size() / 9; i++) {
					element = currentLevel.get(9 * i);
					element.tabs += 1;
					parentLevel.add(element);
				}
				element = currentLevel.get(currentLevel.size() - 5);
				element.tabs += 1;
				parentLevel.add(element);
			} else {
				for (int i = 1; i < currentLevel.size() / 9 + 1; i++) {
					element = currentLevel.get(9 * i);
					element.tabs += 1;
					parentLevel.add(element);
				}
			}
			currentLevel = parentLevel;
		}

		for (int i = 0; i < viewIndexs.size(); i++) {
			ViewIndex line = viewIndexs.get(i);
			for (int j = line.tabs; j < levelNumber-1; j++)
				result += "\t";
			if (line.recordID != -1) {
				result += line.key + " " + line.recordID + "\n";
			} else {
				result += line.key + "\n";
			}
		}

		return result;
	}

	protected class ViewIndex {
		public ViewIndex(String key, int recordID, int tabs) {
			this.key = key;
			this.recordID = recordID;
			this.tabs = tabs;
		}

		String key;
		int recordID;
		int tabs;
	}

	protected void insertRecord(Record record) {
		bPlusTree.insert(record);
		++modCountIndex;
	}

	protected void deleteRecord(Record record) {
		bPlusTree.delete(record.getKey(column), record.getRecordID());
		++modCountIndex;
	}

	// create and return an index iterator
	public Iterator<Integer> iterator(String key) {
		if (!alive) {
			System.out.println("Error: the Index has been dropped");
			return null;
		}
		// if (bPlusTree.find(key) == null) {
		// System.out.println("Error: can't find the key");
		// return null;
		// }
		return new IndexIterator(key);
	}

	// An private Iterator implement class, implement Iterator interface
	private class IndexIterator implements Iterator<Integer> {
		protected IndexIterator(String key) {
			recordArray = bPlusTree.find(key);
			if (recordArray == null) { // for the key that doesn't exist
				recordArray = new RecordArray("");
			}
			numLeft = recordArray.size();
			expectedModCount = recordArray.getModCount();
			this.key = key;
		}

		String key;
		int numLeft;
		int expectedModCount;
		int expectedModCountIndex = modCountIndex;
		int lastPosition = -1;
		RecordArray recordArray;

		@Override
		public boolean hasNext() {
			// if (expectedModCount != recordArray.getModCount()||
			// expectedModCountIndex != modCountIndex) {
			// throw new ConcurrentModificationException();
			// }
			return numLeft > 0;
		}

		@Override
		public Integer next() {
			// System.out.println(modCountIndex);
			if (expectedModCount != recordArray.getModCount()
					|| expectedModCountIndex != modCountIndex) {
				throw new ConcurrentModificationException();
			}
			try {
				int index = recordArray.size() - numLeft;
				Integer recordID = recordArray.get(index);
				lastPosition = index;
				numLeft--;
				return recordID;
			} catch (IndexOutOfBoundsException e) {
				throw new NoSuchElementException();
			}
		}

		@Override
		public void remove() {
			if (lastPosition == -1) {
				throw new IllegalStateException();
			}
			if (expectedModCount != recordArray.getModCount()
					|| expectedModCountIndex != modCountIndex) {
				throw new ConcurrentModificationException();
			}
			try {
				if (lastPosition == recordArray.size() - numLeft) {
					numLeft--; // we're removing after a call to previous()
				}
				// delete the record from DataFile
				Map<String, DataFile> openedFiles = DataManager
						.getOpenedFiles();
				DataFile dataFile = openedFiles.get(fileName);
				records = dataFile.deleteRecord(recordArray.get(lastPosition));
				--modCountIndex;
			} catch (IndexOutOfBoundsException e) {
				throw new ConcurrentModificationException();
			}
			recordArray.changeModCount();
			expectedModCount = recordArray.getModCount();
			lastPosition = -1;
		}
	}

	protected boolean IsAlive() {
		return alive;
	}

	protected void drop() {
		alive = false;
		bPlusTree = null;
		records = null;
	}

	private boolean alive = true;
	private String indexName;
	private String fileName;
	private String column;
	private BPlusTree bPlusTree;
	private Vector<Record> records;
	private int validNumber;
	private transient int modCountIndex;

	protected int getValidNumber() {
		return validNumber;
	}

	protected void setValidNumber(int validNumber) {
		this.validNumber = validNumber;
	}

	// only for test
	protected Iterator<RecordArray> getBPlusTreeIterator() {
		if (!alive) {
			System.out.println("Error: the Index has been dropped");
			return null;
		}
		return bPlusTree.iterator();
	}

	private class BPlusTree implements Serializable {
		/**
		 * 
		 */
		private static final long serialVersionUID = 1L;

		public BPlusTree(Vector<Record> records) {
			this(records, 8);
		}

		// create and return an BPlusTree iterator
		public Iterator<RecordArray> iterator() {
			return new BPlusTreeIterator();
		}

		// currently not support ConcurrentModificationException()
		private class BPlusTreeIterator implements Iterator<RecordArray> {
			public BPlusTreeIterator() {
				endNode = findFirstEndNode();
				currentIndexInsideNode = -1;
				// expectedModCount = recordArray.getModCount();
			}

			EndNode endNode;
			int expectedModCount;
			int currentIndexInsideNode;

			@Override
			public boolean hasNext() {
				if (currentIndexInsideNode != (endNode.size() - 1)) {
					return true;
				} else {
					if (endNode.nextNode != null) {
						return true;
					} else {
						return false;
					}
				}
			}

			@Override
			public RecordArray next() {
				try {
					if (currentIndexInsideNode != (endNode.size() - 1)) {
						++currentIndexInsideNode;
					} else {
						endNode = endNode.nextNode;
						currentIndexInsideNode = 0;
					}
					return (RecordArray) (endNode.children[currentIndexInsideNode]);
				} catch (IndexOutOfBoundsException e) {
					throw new NoSuchElementException();
				}
			}

			@Override
			public void remove() {
				System.out
						.println("forbidden to call this function BPlusTree.Interator.remove()");
			}
		}

		public String printTree() {
			return root.printKey("");
		}

		public EndNode findFirstEndNode() {
			// TODO Auto-generated method stub
			Node node = bPlusTree.root;
			int depth = bPlusTree.treeDepth;
			while (--depth != 0) {
				node = (Node) (node.children[0]);
			}
			return (EndNode) node;
		}

		public BPlusTree(Vector<Record> records, int m) {
			this.m = m;
			treeDepth = 1;
			root = new EndNode();
			Iterator<Record> it = records.iterator();
			while (it.hasNext()) {
				insert((Record) it.next());
			}
		}

		public void insert(Record record) {
			String key = record.getKey(column);
			Node node = root;
			Stack<Node> stack = new Stack<Node>();
			// record the full nodes on the road continuous near the endNode
			int depth = treeDepth;
			while (--depth != 0) {
				if (node.isFull()) { // if the node is full, add it into stack
					stack.push(node);
				} else { // it the node is not full, clear the stack
					stack.clear();
					stack.push(node);
				}
				node = (Node) node.findNextLevelNode(key);
			}
			EndNode endNode = (EndNode) node;
			RecordArray recordArray = endNode.findRecord(key);
			if (recordArray != null) {
				// the key has already been in the tree, add the record to the
				// record list
				recordArray.addElement(record.getRecordID());
			} else { // the key is not in the tree, add key to the tree
				Object child = record;
				Node oldNode = endNode;
				Node newNode;
				while (oldNode.isFull()) { // split the old node
					if (oldNode instanceof EndNode) { // new EndNode
						newNode = new EndNode();
					} else { // new IndexNode
						newNode = new IndexNode();
					}
					key = oldNode.split(newNode, key, child);// split(oldNode,
																// newNode, key,
																// child);
					if (stack.empty()) { // root is also full
						// increase the depth of tree and split it.
						root = new IndexNode(key, oldNode, newNode);
						treeDepth++;
						return;
					}
					oldNode = stack.pop();
					// key = newNode.leastKey();
					child = newNode;
				}
				// insert the key directly into the node
				oldNode.insertKey(key, child);
			}
		}

		public void delete(final String key, final int RecordID) {
			Node node = root;
			Stack<Node> stack = new Stack<Node>();
			// record the half nodes on the road continuous near the endNode
			int depth = treeDepth;
			while (--depth != 0) {
				if (node.isHalf()) { // if the node is half, add it into stack
					stack.push(node);
				} else { // it the node is not half, clear the stack
					stack.clear();
					stack.push(node);
				}
				node = (Node) node.findNextLevelNode(key);
			}
			EndNode endNode = (EndNode) node;
			RecordArray recordArray = endNode.findRecord(key);
			if (recordArray == null) {
				// can't find key throw exception
				System.out.println("can't find delete item in the b plus tree");
			} else { // find the key
				if (recordArray.size() != 1) { // if more than one record,
												// delete the record from record
												// array.
					recordArray.removeRecordID(RecordID);
				} else { // if only one record in current key, delete the key
					if (!endNode.isHalf()) { // if current node has more than
												// half keys, then just delete
												// the key
						endNode.deleteKey(key);
						return;
					} else { // if current node only has half keys, then do
								// balance
						endNode.deleteKey(key);
						Node parentNode = null;
						Node currentNode = endNode;
						while (!stack.empty()) { // If it is root, then exit.
							parentNode = stack.pop();
							// Borrow left. if left node has more than half
							// keys, then borrow
							Node leftNode = (Node) ((IndexNode) parentNode)
									.leftSibling(currentNode);
							if (leftNode != null && !leftNode.isHalf()) {
								currentNode.leftBorrow(leftNode, parentNode);
								return;
							}
							// Borrow right. if left has more than half-full
							// element, then borrow
							Node rightNode = (Node) ((IndexNode) parentNode)
									.rightSibling(currentNode);
							if (rightNode != null && !rightNode.isHalf()) {
								currentNode.rightBorrow(rightNode, parentNode);
								return;
							}
							// merge left. If there is left sibling, merge it.
							// it must has one left node or right node, because
							// it is not root
							if (leftNode == null) {
								leftNode = currentNode;
								currentNode = rightNode;
							}
							currentNode.leftMerge(leftNode, parentNode);
							// if after merge, the parent node is empty, then
							// set the left node as the root and decrease the
							// depth of tree
							if (parentNode.isEmpty()) {
								root = leftNode;
								treeDepth--;
								return;
							}
							currentNode = parentNode;
						}
					}
				}
			}
		}

		public RecordArray find(String key) {
			Node node = root;
			int depth = treeDepth;
			while (--depth != 0) {
				node = (Node) node.findNextLevelNode(key);
			}
			EndNode endNode = (EndNode) node;
			return endNode.findRecord(key);
		}

		int m; // the maximum number of keys in the B plus tree node.
		int treeDepth;
		Node root;

		// node abstract class
		protected abstract class Node implements Serializable {
			/**
			 * 
			 */
			private static final long serialVersionUID = 1L;

			// reversely print the whole B plus tree
			public abstract String printKey(String table);

			// delete a key from a node
			public abstract void deleteKey(String key);

			// borrow one key from left sibling
			public abstract void leftBorrow(Node leftNode, Node parentNode);

			// borrow one key from right sibling
			public abstract void rightBorrow(Node rightNode, Node parentNode);

			// merge current node into left sibling, right merge is implemented
			// in the similar way
			public abstract void leftMerge(Node leftNode, Node parentNode);

			// insert one key into current node
			public abstract void insertKey(String key, Object ob);

			// split the current node into two node
			public abstract String split(Node newNode, String key, Object child);

			public Node() {
				numOfKey = 0;
				keys = new String[m + 1]; // for split
			}

			public boolean isEmpty() {
				return numOfKey == 0;
			}

			public boolean isFull() {
				return numOfKey == m;
			}

			public boolean isHalf() {
				return numOfKey == m / 2;
			}

			// replace the old key with new key
			public void replaceKey(String oldKey, String newKey) {
				for (int i = 0; i < numOfKey; i++) {
					if (oldKey.compareTo(keys[i]) == 0) {
						keys[i] = newKey;
						return;
					}
				}
			}

			// find next node
			public Object findNextLevelNode(String key) {
				for (int i = 0; i < numOfKey; i++) {
					if (key.compareTo(keys[i]) < 0)
						return children[i];
				}
				return children[numOfKey];
			}

			int numOfKey;
			String[] keys;
			Object[] children;

			// private void readObject(java.io.ObjectInputStream stream)
			// throws IOException, ClassNotFoundException {
			// numOfKey = stream.readInt();
			// keys = (String[]) stream.readObject();
			// }
			//
			// private void writeObject(java.io.ObjectOutputStream stream)
			// throws IOException {
			// stream.writeInt(numOfKey);
			// stream.writeObject(keys);
			// }
		}

		// Index node class extends class Node
		private class IndexNode extends Node implements Serializable {

			/**
			 * 
			 */
			private static final long serialVersionUID = 1L;

			// used for increase the depth of tree, new root node
			public IndexNode(String key, Node leftHandSide, Node rightHandSide) {
				this();
				keys[numOfKey] = key;
				children[numOfKey] = leftHandSide;
				numOfKey++;
				children[numOfKey] = rightHandSide;
			}

			public IndexNode() {
				super();
				children = new Node[m + 2]; // for split
			}

			// find the middle key between left child and right child
			public String findMiddleKey(Node leftNode, Node rightNode) {
				for (int i = 0; i < numOfKey; i++) {
					if (children[i] == leftNode) {
						return keys[i];
					}
				}
				System.out
						.println("method findMiddleKey error: can't find the middle key");
				return null;
			}

			// check whether the child has a left sibling
			public Object leftSibling(Object child) {
				for (int i = 0; i < numOfKey + 1; i++) {
					if (children[i] == child) {
						if (i > 0)
							return children[i - 1];
						else
							break;
					}
				}
				return null;
			}

			// check whether the child has a right sibling
			public Object rightSibling(Object child) {
				for (int i = 0; i < numOfKey + 1; i++) {
					if (children[i] == child) {
						if (i < numOfKey)
							return children[i + 1];
						else
							break;
					}
				}
				return null;
			}

			// insert a key and a child into node
			@Override
			public void insertKey(String key, Object child) {
				int i;
				// find the right postion
				for (i = numOfKey; i > 0; i--) {
					if (key.compareTo(keys[i - 1]) < 0) {
						keys[i] = keys[i - 1];
						children[i + 1] = children[i];
					} else
						break;
				}
				// add the new key and child into node
				keys[i] = key;
				children[i + 1] = (Node) child;
				numOfKey++;
			}

			// recursively print the whole B plus tree
			@Override
			public String printKey(String table) {
				table += "\t";
				String result = "";
				// print key and children one after another
				for (int i = 0; i < numOfKey; i++) {
					result += ((Node) children[i]).printKey(table);
					result += table + keys[i] + "\n";
					// System.out.println(table + keys[i]);
				}
				result += ((Node) children[numOfKey]).printKey(table);
				return result;
			}

			// split the node into two nodes
			// 1. insert the key and child into the node, then the node has 9
			// keys, 10 children
			// 2. find the middle key as the new upper level key
			// 3. evenly assign half of keys and children into two nodes
			@Override
			public String split(Node newNode, String key, Object child) {
				// 1. insert the key and child
				insertKey(key, child);
				// 2. find middle key
				String splitKey = keys[numOfKey / 2];
				newNode.numOfKey = numOfKey / 2;
				keys[numOfKey / 2] = null;
				numOfKey /= 2;
				// copy the half of keys and children into new node
				int i = 0;
				for (; i < numOfKey; i++) {
					newNode.keys[i] = keys[numOfKey + i + 1];
					keys[numOfKey + i + 1] = null;
					newNode.children[i] = children[numOfKey + i + 1];
					children[numOfKey + i + 1] = null;
				}
				newNode.children[i] = children[numOfKey + i + 1];
				children[numOfKey + i + 1] = null;
				return splitKey;
			}

			// borrow one key and child from left sibling
			@Override
			public void leftBorrow(Node leftNode, Node parentNode) {
				// System.out.println("indexnode left borrow");
				// delete the last key and child from left node
				Object child = leftNode.children[leftNode.numOfKey];
				leftNode.children[leftNode.numOfKey] = null;
				leftNode.numOfKey--;
				String key = leftNode.keys[leftNode.numOfKey];
				leftNode.keys[leftNode.numOfKey] = null;
				// change the parent middle key with the last left node key
				String middleKey = ((IndexNode) parentNode).findMiddleKey(
						leftNode, this);
				parentNode.replaceKey(middleKey, key);
				// insert the middle key and child into the head of the node
				for (int i = numOfKey; i > 0; i--) {
					keys[i] = keys[i - 1];
					children[i + 1] = children[i];
				}
				children[1] = children[0];
				keys[0] = middleKey;
				children[0] = child;
				numOfKey++;
			}

			// borrow one key and child from right sibling
			@Override
			public void rightBorrow(Node rightNode, Node parentNode) {
				// System.out.println("indexnode right borrow");
				// delete the first key and child from right node
				Object child = rightNode.children[0];
				String key = rightNode.keys[0];
				rightNode.numOfKey--;
				for (int i = 0; i < rightNode.numOfKey; i++) {
					rightNode.keys[i] = rightNode.keys[i + 1];
					rightNode.children[i] = rightNode.children[i + 1];
				}
				rightNode.children[rightNode.numOfKey] = rightNode.children[rightNode.numOfKey + 1];
				rightNode.children[rightNode.numOfKey + 1] = null;
				rightNode.keys[rightNode.numOfKey] = null;
				// change the parent middle key with the last left node key
				String middleKey = ((IndexNode) parentNode).findMiddleKey(this,
						rightNode);
				parentNode.replaceKey(middleKey, key);
				// insert the middle key and child into the tail of the node
				keys[numOfKey] = middleKey;
				numOfKey++;
				children[numOfKey] = child;
			}

			// merge the current node with left node
			@Override
			public void leftMerge(Node leftNode, Node parentNode) {
				// System.out.println("indexnode merge");
				// find the middle key between two children
				String key = ((IndexNode) parentNode).findMiddleKey(leftNode,
						this);
				parentNode.deleteKey(key); // delete key from parent node
				// add the key into left node
				leftNode.keys[leftNode.numOfKey] = key;
				// copy all the keys and links in the node to leftNode
				leftNode.children[leftNode.numOfKey + 1] = children[0];
				for (int i = 0; i < numOfKey; i++) {
					leftNode.keys[leftNode.numOfKey + 1 + i] = keys[i];
					leftNode.children[leftNode.numOfKey + 2 + i] = children[i + 1];
				}
				leftNode.numOfKey = m;
			}

			// delete the key and child from the node, move the right side
			// elements one cell left
			@Override
			public void deleteKey(String key) {
				for (int i = 0; i < numOfKey; i++) {
					if (key.compareTo(keys[i]) < 0) {
						keys[i - 1] = keys[i];
						children[i] = children[i + 1];
					}
				}
				numOfKey--;
				keys[numOfKey] = null;
				children[numOfKey + 1] = null;
			}

			// private void readObject(java.io.ObjectInputStream stream)
			// throws IOException, ClassNotFoundException {
			// super.readObject(stream);
			// children = (Node[]) stream.readObject();
			// }
			//
			// private void writeObject(java.io.ObjectOutputStream stream)
			// throws IOException {
			// super.writeObject(stream);
			// stream.writeObject((Node[]) children);
			// }
		}

		// Lowest level node extends class Node
		private class EndNode extends Node implements Serializable {
			/**
			 * 
			 */
			private static final long serialVersionUID = 1L;

			public EndNode() {
				super();
				children = new RecordArray[m + 1]; // for split
			}

			// delete the key and child from the node, move the right side
			// elements one cell left
			@Override
			public void deleteKey(String key) {
				for (int i = 0; i < numOfKey; i++) {
					if (key.compareTo(keys[i]) < 0) {
						keys[i - 1] = keys[i];
						children[i - 1] = children[i];
					}
				}
				numOfKey--;
				keys[numOfKey] = null;
				children[numOfKey] = null;
			}

			// split the node into two nodes
			// 1. evenly assign half of keys and children into two nodes
			// 2. insert the new key and child into one of the nodes
			@Override
			public String split(Node newNode, String key, Object child) {
				// 1. evenly assign half of keys and children into two nodes
				newNode.numOfKey = numOfKey / 2;
				numOfKey /= 2;
				for (int i = 0; i < numOfKey; i++) {
					newNode.children[i] = children[numOfKey + i];
					children[numOfKey + i] = null;
					newNode.keys[i] = keys[numOfKey + i];
					keys[numOfKey + i] = null;
				}
				// 2. insert the new key and child into one of the nodes
				if (key.compareTo(newNode.keys[0]) < 0) {
					insertKey(key, child);
				} else {
					newNode.insertKey(key, child);
				}
				// set the next node pointer
				((EndNode) newNode).nextNode = ((EndNode) this).nextNode;
				((EndNode) this).nextNode = (EndNode) newNode;
				return newNode.keys[0];
			}

			// find record array according to the key value
			public RecordArray findRecord(String key) {
				if (numOfKey == 0)
					return null;
				if (key.compareTo(keys[0]) < 0)
					return null;
				if (key.compareTo(keys[numOfKey - 1]) > 0)
					return null;
				for (int i = 0; i < numOfKey; i++) {
					if (key.compareTo(keys[i]) == 0)
						return (RecordArray) children[i];
					if (key.compareTo(keys[i]) < 0)
						return null;
				}
				return null;
			}

			// insert a key and a child into node
			@Override
			public void insertKey(String key, Object child) {
				// find the right position
				int i;
				for (i = numOfKey; i > 0; i--) {
					if (key.compareTo(keys[i - 1]) < 0) {
						keys[i] = keys[i - 1];
						children[i] = children[i - 1];
					} else {
						break;
					}
				}
				// insert
				keys[i] = key;
				children[i] = new RecordArray(key);
				// insert record ID
				((RecordArray) children[i]).addElement(((Record) child)
						.getRecordID());
				numOfKey++;
			}

			// recursively print the key of b plus tree
			@Override
			public String printKey(String table) {
				table += "\t";
				String result = "";
				// print key and RecordID one by one
				for (int i = 0; i < numOfKey; i++) {
					// System.out.print(table + keys[i] + "\t");
					result += table + keys[i];// + "\t";
					result += ((RecordArray) children[i]).printRecordID();
					// System.out.println("");
					result += "\n";
				}
				return result;
			}

			// borrow one key and child from left sibling
			@Override
			public void leftBorrow(Node leftNode, Node parentNode) {
				// System.out.println("endnode left borrow");
				// delete the last key and child from left node
				leftNode.numOfKey--;
				String key = leftNode.keys[leftNode.numOfKey];
				leftNode.keys[leftNode.numOfKey] = null;
				Object child = leftNode.children[leftNode.numOfKey];
				leftNode.children[leftNode.numOfKey] = null;
				// change the parent middle key with the last key of left node
				String middleKey = ((IndexNode) parentNode).findMiddleKey(
						leftNode, this);
				parentNode.replaceKey(middleKey, key);
				// add the new key into the node
				for (int i = numOfKey; i > 0; i--) {
					keys[i] = keys[i - 1];
					children[i] = children[i - 1];
				}
				numOfKey++;
				keys[0] = key;
				children[0] = child;
			}

			// borrow one key and child from right sibling
			@Override
			public void rightBorrow(Node rightNode, Node parentNode) {
				// System.out.println("endnode right borrow");
				// delete the first key and child from rightNode
				rightNode.numOfKey--;
				String key = rightNode.keys[0];
				Object child = rightNode.children[0];
				for (int i = 0; i < rightNode.numOfKey; i++) {
					rightNode.keys[i] = rightNode.keys[i + 1];
					rightNode.children[i] = rightNode.children[i + 1];
				}
				rightNode.keys[rightNode.numOfKey] = null;
				rightNode.children[rightNode.numOfKey] = null;
				// change the middle key of parent node with the new least key
				// of right node
				String middleKey = ((IndexNode) parentNode).findMiddleKey(this,
						rightNode);
				parentNode.replaceKey(middleKey, rightNode.keys[0]);
				// add the key and child to the tail of node
				keys[numOfKey] = key;
				children[numOfKey] = child;
				numOfKey++;
			}

			// merge the current into left sibling
			@Override
			public void leftMerge(Node leftNode, Node parentNode) {
				// System.out.println("endnode merge");
				// find the middle key between two children
				String key = ((IndexNode) parentNode).findMiddleKey(leftNode,
						this);
				parentNode.deleteKey(key); // delete key from parent node
				// copy all the keys and links in the node to leftNode
				for (int i = 0; i < numOfKey; i++) {
					leftNode.keys[leftNode.numOfKey + i] = keys[i];
					leftNode.children[leftNode.numOfKey + i] = children[i];
				}
				leftNode.numOfKey = m - 1;
				// set the next node
				((EndNode) leftNode).nextNode = nextNode;
			}

			// right sibling node
			private EndNode nextNode;

			// private void readObject(java.io.ObjectInputStream stream)
			// throws IOException, ClassNotFoundException {
			// super.readObject(stream);
			// children = (RecordArray[]) stream.readObject();
			// nextNode = (EndNode) stream.readObject();
			// }
			//
			// private void writeObject(java.io.ObjectOutputStream stream)
			// throws IOException {
			// super.writeObject(stream);
			// stream.writeObject((RecordArray[]) children);
			// stream.writeObject(nextNode);
			// }

			public int size() {
				return numOfKey;
			}
		}

	}

	// store record ID with same key
	protected class RecordArray implements Serializable {
		/**
		 * 
		 */
		private static final long serialVersionUID = 1L;

		private transient int modCount;

		void changeModCount() {
			modCount++;
		}

		int getModCount() {
			return modCount;
		}

		private String key;

		protected String getKey() {
			return key;
		}

		public RecordArray(String key) {
			this.key = key;
			recordsID = new Vector<Integer>();
			modCount = 0;
		}

		// remove the record from the record array by record ID
		public void removeRecordID(int recordID) {
			Iterator<Integer> it = recordsID.iterator();
			while (it.hasNext()) {
				if (it.next() == recordID) {
					it.remove();
					break;
				}
			}
			changeModCount();
		}

		// remove the record by position supporting iterator
		public void remove(int lastPosition) {
			recordsID.remove(lastPosition);
		}

		public int size() {
			return recordsID.size();
		}

		public void addElement(Integer recordID) {
			recordsID.add(recordID);
			changeModCount();
		}

		private Vector<Integer> recordsID;

		// sequentially print the record ID in the record array
		public String printRecordID() {
			String result = "";
			Iterator<Integer> it = recordsID.iterator();
			while (it.hasNext()) {
				// System.out.print(" " + it.next());
				result += " " + it.next();
			}
			return result;
		}

		public Integer get(int index) {
			return recordsID.get(index);
		}

		// public boolean isEmpty() {
		// return recordsID.isEmpty();
		// }

		// @SuppressWarnings("unchecked")
		// private void readObject(java.io.ObjectInputStream stream)
		// throws IOException, ClassNotFoundException {
		// recordsID = (Vector<Integer>) stream.readObject();
		// }
		//
		// private void writeObject(java.io.ObjectOutputStream stream)
		// throws IOException {
		//
		// // serialize the records ID
		// stream.writeObject(recordsID);
		// }

		private void updateRecordID() {
			// update all the recordID
			for (int i = 0; i < recordsID.size(); i++) {
				int recordID = recordsID.get(i);
				recordsID.set(i, records.get(recordID).getRecordID());
			}
		}
	}

	protected void updateRecordID(Vector<Record> newNecords) {
		// traverse whole B Plus Tree and update recordID for each record
		Iterator<RecordArray> it = bPlusTree.iterator();
		while (it.hasNext()) {
			it.next().updateRecordID();
		}
		this.records = newNecords;
	}
}
